package Offer;

import java.util.ArrayList;
import java.util.List;

//Offer12.矩阵中的路径
//本题需要注意的地方：下一步移动的位置不能是上一次移动的位置 => 已经使用过的，不能再用了
public class Offer12 {
    public boolean exist(char[][] board, String word) {
        char start = word.charAt(0);
        //寻找start
        int i = 0, j = 0;
        //把所有start的可能存到list中，然后分别对list的所有可能进行寻找
        List<Integer> listI = new ArrayList<>();
        List<Integer> listJ = new ArrayList<>();
        for (; i < board.length; i++) {
            for (j = 0; j < board[0].length; j++) {
                if (board[i][j] == start) {
                    listI.add(i);
                    listJ.add(j);
                }
            }
        }
        if (listI.size() == 0)
            return false;
        //开始寻找，使用dfs
        int count = 0;
        boolean[][] used = new boolean[board.length][board[0].length];

        while (listI.size() != 0) {
            int I = listI.remove(listI.size() - 1);
            int J = listJ.remove(listJ.size() - 1);
            if (dfs(board, word, count, I, J, used)) {
                return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int count, int i, int j, boolean[][] used) {
        if (count == word.length())
            return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
            return false;
        char c = word.charAt(count);
        if (board[i][j] != c || used[i][j]) {
            return false;
        } else {
            used[i][j] = true;
        }
        //左
        boolean left = dfs(board, word, count + 1, i, j - 1, used);
        //右
        boolean right = dfs(board, word, count + 1, i, j + 1, used);
        //上
        boolean up = dfs(board, word, count + 1, i - 1, j, used);
        //下
        boolean down = dfs(board, word, count + 1, i + 1, j, used);
        if (left || right || up || down)
            return true;
        used[i][j] = false;
        return false;
    }

    public static void main(String[] args) {
        Offer12 offer = new Offer12();
//        boolean boo = offer.exist(new char[][]{{'a', 'b', 'c', 'e'},{'s','f','c','s'},{'a','d','e','e'}}, "abcced");
        boolean boo = offer.exist(new char[][]{{'a', 'b'}, {'c', 'd'}}, "cdba");
        System.out.println(boo);
    }
}
